Good afternoon, I would like to start by introducing myself. I am Jon Kalb and I work for Liberty Software a Macintosh-only Software Consulting firm in the bay area.
Although I have written shipping code that makes heavy used of the Standard Template Library, I don't hold myself out as an expert. My goal for this session is not explore STL in detail or to get into advanced or even intermediate topics. My goal is to provide an introduction to experienced C++ programmers that have little or no experience with STL.
If you are an experienced STL user, that's great because, later in this talk I will give you a chance to share some of your hard-won knowledge.
STL, or the Standard Template Library, is now a part of the draft ANSI C++ Standard. Users of STL can begin to expect it to be universally available. For those of us that are not yet familiar with STL, the future is clear-professional C++ programmers will be expected to understand and maintain objects that depend on this new library.
STL code will probably look a little strange at first and learning how to use the library will require some effort. Fortunately, STL's power, ease of use, and consistency make it worthwhile.
My focus here is going to be on giving you the information you need to begin to use STL in your code. This discussion will be about practice, not theory, which is, in a way, a shame, because the thinking behind how the library is structured and used is very interesting and fun to explore. You will see that very little knowledge of templates is needed for getting started. Only when you are ready to extend the library is writing templates required.
Before we plunge into the code-level nitty-gritty, I do want to give us an overview of what it is that STL is trying to accomplish. I feel that this perspective is valuable, because I know how lost I was without it.
I was first drawn to STL as a standard container library. But as I read about STL, I was impatient that STL writers tend to start off by talking about generic algorithms, function objects, and/or iterators. If STL is about building a better list clas, than why start off with these side topics?
It turns out that STL is not about containers. STL is really about generic algorithms. Containers are just a necessary step to reaching generic algorithm nirvana.
As an example of a generic algorithm, consider qsort(). qsort() is an ANSI C implementation of a generic algorithm. Regardless of the contents of your array, your data is sorted.
qsort() from <stdlib.h> An ANSI C Generic Algorithm
void qsort( void *base,
size_t nmemb,
size_t size,
int(*compare)(const void *, const void *));
where: base is a pointer to an array
nmemb is the number of elements in the array
size is the size of each array element
compare is a pointer to a function defined as:
int compare(const void *e1, const void *e2);
where: e1 and e2 are elements pointers
returns if
< 0 (*e1) < (*e2)
0 (*e1) == (*e2)
> 0 (*e1) > (*e2)
When subtraction is a valid operations for elements
of type T, the compare funtion can be implemented as:
{
return (int)((*(T *)e1) - (*(T *)e2));
}
But consider the limitation of this kind of generic algorithm.
First, every use of qsort() requires that we code a "compare" function, even if this function is trivial. Of course, if the compare is trivial, then dereferencing a function pointer is pretty inefficient. Whether or not we care depends on the relative time spent in compares as opposed to swaps. For most uses of qsort() this may not be significant, but it points up a weakness of this approach to generic algorithms.
Next, we have no control over construction, destruction, or assignment of the array items being sorted. All swapping is done by raw memory moves.
Also, by using void pointers, we have completely sacrificed type safety.
Finally, we are restricted to working with arrays and these must exist in the standard memory model. God, and the ANSI Standard, forbid that you use an unconventionally memory model or that your data be in a list, a tree, a file, or any container other than a simple array.
These limitations can all be overcome, and have been in STL, by the use of templates.
SLIDE OFF
Before looking at the STL equivalent of qsort() I want to present a quick and dirty definition.
One of the basic building blocks of STL is the iterator. For now, I want to define an iterator as anything that can take the deference operator or, to put it another way, if it can take pointer syntax, it's an iterator.
quick and dirty iterator definition
If this makes sense:
object == *thing;
Then "thing" is an iterator.
char *a = "";
'\0' == *a;
All pointers are iterators.
For now, when you hear iterator, think pointer.
Now let's look at STL's version of the quick sort algorithm:
STL sort from <algo.h> or <algorithm> An STL Generic Algorithm
template <class RandomAccessIterator>
void sort( RandomAccessIterator first,
RandomAccessIterator last) {...}
template <class RandomAccessIterator, class Compare>
void sort( RandomAccessIterator first,
RandomAccessIterator last,
Compare comp) {...}
where our quick and dirty translation is:
void sort(pointer first, pointer last);
(Uses "<" to compare elements.)
void sort(pointer first, pointer last, Compare funct *comp);
Instead of passing an array's base address and the number and size of elements in the array we pass a pair of iterators (think pointers). Due to template magic, these iterators are type safe. We need not pass in the element size because, like type safe pointers, we can safely increment and decrement as needed.
Passing two iterators is the standard way of passing a collection of items in STL. The first iterator refers to the first item in the collection, but the second iterator, despite its name, does not refer to the last. The convention is that the second iterator points one past the last item in the collection.
Using this convention, the two iterators exactly enclose all and only the elements to be considered.
iterating over an STL collection
A set of data is represented in STL by a pair of
iterators. The first iterator references the first
element and the last iterator references one past
the last element. This is represented in half-open
interval notation as:
[first, last)
Iterating:
Instead of the typical C iteration:
for (i = 0; i < count; ++i)
{
arrayBase[i]; /* element */
}
We use:
for (i = first; i != last; ++i)
{
(*i); // dereferenced object
}
Never dereference the "last" iterator. It can
only be used for comparing with the "first"
iterator.
(*last) is undefined.
This may take some getting used to at first, but, on reflection, it makes a great deal of sense. Because the iterators may be pointers into a list, we can't rely on the standard "less than" comparison that we are used to. As we iterate over our collection, we just need to increment our "first" iterator and compare it to our "last" iterator. When the iterators are equal (which, by definition, means that they refer to the same item), then we are done.
Note that we never dereference the "last" iterator. It may be nil or any other value. It can only be used to compare with the "first" iterator. You should always assume that dereferencing it will bus error.
STL sort from <algo.h> or <algorithm> An STL Generic Algorithm
template <class RandomAccessIterator>
void sort( RandomAccessIterator first,
RandomAccessIterator last) {...}
template <class RandomAccessIterator, class Compare>
void sort( RandomAccessIterator first,
RandomAccessIterator last,
Compare comp) {...}
where our quick and dirty translation is:
void sort(pointer first, pointer last);
(Uses "<" to compare elements.)
void sort(pointer first, pointer last, Compare funct *comp);
Returning to the STL sort declarations, we see that the first declaration does not take a comparison functio. If no comparison function is passed, the STL sort implementation will simply use the "less than" operator for comparison (of the items, not the iterators). At first glance, this may seem to be of little use, but since template magic gives us type safety, the objects to be sorted can overload the "less than" operator. Without our having to code a comparison function, the objects are sorted into their "natural" order.
SLIDE OFF
In our first sample program I demonstrate the efficiency that we can achieve with templates. Often new coding technologies offer us a trade-off with power of expression or ease of use on one side and performance on the other side. This program compares quick sorting an array with qsort() and the STL sort() generic algorithm.
#include <iostream>
int ANSICqsortCompare(const void *el1, const void *el2);
int ANSICqsortCompare(const void *el1, const void *el2)
{
return (int)(*(long *)el1 - *(long *)el2);
}
void main(void)
{
cout << "STL sort sample!\n\n"; // setting up arrays
I tested this on both 68K and PowerPC machines with both the HP STL and the Modina STL implementations. The STL sort was from three to twelve times faster.
Of course, I stacked the deck with this sample program. Because the objects being sorted were of a built-in type (they are longs) and because we used the form of sort() that does not use a "compare" function object we don't have any function call overhead when doing compares. But that is my point. Template magic allows us to implement a generic algorithm that, in some cases, doesn't require functional call overhead, when the traditional approach would always require it.
My point is not that generic algorithms are more efficient than specifically coded algorithms my point is that, using templates, we can be more efficient than using the traditional approaches to generic algorithms.
SLIDE OFF
Now that we have tasted generic algorithms, we have a better idea of why implementing them leads us to iterators and containers. The whole point of generic algorithms is that the work that needs to be done does not depend on the kind of data involved.
If a class of objects supports addition, then we can accumulate. If it supports addition and division by a scalar then we can average. If it supports the "less than" operator, then we can sort. It doesn't matter if the class represents ints, floats, strings, test scores, portfolios, medical records, or box scores. It also doesn't matter if the items are stored in an array, a list, a file, or on a web server.
If our generic algorithms only worked on items that are passed to them, like min and max, then we would have no need of iterators or containers.
Most generic algorithms are designed for an arbitrary number of items. This is why we have iterators. With this single piece of information we can get the value of an item (by dereferencing) or move to the next item in the collection (by incrementing or decrementing).
SLIDE OFF
If the only containers that we ever used were arrays, then we could just use pointers and forget about this iterator nonsense. The one drawback to pointers is that they don't hide the container from the generic algorithm. Because qsort() uses pointers, it can only operate on arrays.
Imagine a linked list. A pointer to an element in the list has part of what we need in an iterator--if we dereference it we have our element. But if we increment this pointer we don't get the next item in the list, we are pointing at some arbitrary memory location.
Now imagine that the we have defined a class of objects that point at items in lists. We can override the increment operator to have the object pointer walk the list. Voila,! We have a list iterator.
This also explains why iterators and containers are so closely linked. The implementation of the iterator is dependent on the nature of the container class.
We are almost ready to get down and dirty with some code, but before we start looking at containers we need to be aware of some restrictions placed on the objects that will be contained.
Theoretical class requirements
Classes whose instances will be stored in STL containers must have:
• a copy constructor
• operator=
If the instances will be sorted or compared then the class must have:
• operator==
• operator<
Practical class requirements
In practice, it may be necessary to please the compiler gods by
defining some functions that are never called. The practical list of
requirements is:
• a default constructor
• a copy constructor
• operator=
• operator==
• operator<
OK, let's look at containers and their iterators. We already know that we can use arrays and pointers with generic algorithms, now lets look as the other containers that STL defines.
The first containers are called vectors and deques. Vector is not a terrible intuitive name (at least it wasn't for me). The idea is that it grows in only one direction. A vector is like an array except that it can grow, but only at the end. A deque is like an array except that it can grow at both the beginning and the end.
#include <iostream>
#include <deque>
void main(void)
{
// vector<char *> v; // This should be OK. It isn't yet.
vector<char *, allocator<char *> > v; // Required in CW12
// vector<char *, allocator<char *>> v; // ">>" is extraction
assert(v.empty());
v.push_back("sleep");
v.insert(v.end(), "was");
assert(v.size() == 2);
v.push_back("for");
v.push_back("the");
v.push_back("weak");
v.push_back("or");
v.pop_back();
v.push_back("and");
v.push_back("sickly");
v[1] = "is"; // Used to replace existing: "is" for "was"
// v[7] = "DOS users"; // Cannot use this notation to add elements.
In this sample program we play with a vector and a deque.
As the saying goes, "In theory-theory is as good as practice… In practice, it isn't." The STL spec says that we should be able to declare our vector, v as "vector left angle char splat right angle."
As of CW12 or CWPro 1, Metrowerks is not yet quite up to the STL spec, so, for now, we have to add an allocator declaration to each STL container declaration. The second template parameter is supposed to be a default parameter. Since this isn't yet supported as a default parameter, we must specify it explicitly.
Allocators do not fall into scope of this introduction so we won't be saying anymore about them. Just trust me on this, for each container class add ", space allocator left-angle your type right-angle space." Don't forget the last space or your two right angle brackets will merge and become the extraction operator. You don't want to know what your compiler thinks of that.
This code demonstrates several functions of vectors and deques:
empty()
which works the way you would expect for all containers.
push_back()
which is the workhorse for adding to a vector
insert()
which, although I am using it here to insert at the end of the vector, can be used to insert anywhere. Inserting in the middle of a vector or deque can be done, but it is not efficient. If you need to do this often, consider using a list.
pop_back()
erases the last item in the vector or deque.
array notation
both vectors and deques use array notation. This notation returns a reference so it can be used for both reading and writing, but it cannot be used to add elements to the container.
erase()
which can be called to erase a collection by passing two iterators. I want to erase the elements that are the third from the end to the second to the end, but since the iterator should point passed the last item to be erased, I passed d.end() - 3 and d.end() - 1 for the range.
Note how we declare an iterator for our container. We simply restate the container declaration followed by "scope resolution operator iterator." As container declarations tend to get a bit wordy, we often use a typedef to make life easier. I have done that for the deque declaration.
Iterating over the container is just as we discussed earlier and it is identical for both the vector and the deque.
The only other things to notice are the deque constructor, we construct by iterating across the vector, and the push_front() call. Deques can grow at both ends and the efficient way to insert at the beginning of the deque is push_front(). There is also a pop_front. These call is not supported for vectors.
SLIDE OFF
Vectors, deques, and arrays are called sequence containers because they store items in the sequence in which they are added. With one exception, other STL containers store items in sorted order and are called associative containers. The last sequence container is the list.
In this example we see that using a list is similar to the other containers. The biggest differences are in the things that you already know about the differences between array-like classes and lists. Arrays have less overhead and lists are more flexible.
Here we are showing off remove(), sort(), unique(), and reverse(), which are member functions of the list class. This class also has functions to splice() lists together or merge() sorted lists.
But in going from array-like containers to lists we did have to give up some things. We can no longer use array notation or the at() function to address items by their position in the list.
The rest of the STL containers are associative. These containers keep the items they contain in sorted order. As you would expect, at construction, either pass a function to use as a compare function or we use the default "less than" comparison.
Because these containers are always sorted, we no longer use push_back() or push_front(). We can call insert() without passing a positions iterator.
char start[] = "sleep is a poor substitute for caffeine";
MySet s(start, start + strlen(start));
MyMultiSet ms;
ms.insert(start, start + strlen(start));
cout << " start: ";
copy(s.begin(), s.end(), out);
cout << "\n start: ";
copy(ms.begin(), ms.end(), out);
MySet::iterator si1, si2;
MyMultiSet::iterator msi1, msi2;
si1 = s.lower_bound('b');
si2 = s.upper_bound('s');
s.erase(' ');
s.erase(si1, si2);
msi1 = ms.lower_bound('b');
msi2 = ms.upper_bound('s');
ms.erase(' ');
ms.erase(msi1, msi2);
cout << "\nremoved b-s: ";
copy(s.begin(), s.end(), out);
cout << "\nremoved b-s: ";
copy(ms.begin(), ms.end(), out);
cout << "\n";
}
// start: abcefilnoprstu
// start: aabceeeeefffiiilnooopprrsssstttuu
// removed b-s: atu
// removed b-s: aatttuu
In this example we use two of the associative containers, the set and the multiset. The set is a simple ordered collection that differs from the multiset in that it does not support duplicate items.
Both set and multiset have lower_bound() and upper_bound() members. These members return an iterator that refers to the lowest or highest location that an item of the passed value could be placed without violating the ordering rules.
The last two containers that we are going to examine are called the map and the multimap. As you have already guessed, the difference between them is that the multimap can contain duplicate entries.
All of the containers that we have looked at so far have been designed to contain items, but the map is designed to contain pairs of times. Each pair consists of a key and a value. When a pair is added to a map the key is used to find where, in the sort order, this pair belongs.
A map is like a set in which each item in the set has a link to another item that may be of a different type.
In this example, we create a map that maps integers to their names. We create two vectors of integers and use the random_shuffle generic algorithm to shuffle their values. Next we walk the vectors and add and subtract their corresponding values. What makes it interesting is that when we print our results we use the map to replace all the integers with their names.
We can use array notation so that the expression "map sub key" returns the map value.
My final code example deals with exceptions. My best words to you are proceed with caution.
#include <iostream>
#include <deque>
#if comment
The exception hierarchy:
exception root of all exceptions
| |
| bad_alloc memory allocation exception
|
logic_error precondition violation exception root
| | |
| | out_of_range attempt to reference a container
| | using an illegal index
| |
| length_error attempt to create a string with an
| illegal length
|
invalid_argument attempt ot create a container with an
illegal size such as -1
#endif // comment
void main(void)
{
const int limit = 10;
vector<int, allocator<int> > v;
for (int j = 0; j < limit; ++j)
{
v.push_back(j);
}
try
{
int i = v[limit];
cout << i << " no exception for i = v[limit];" << endl;
i = v.at(limit);
cout << i << " no exception i = v.at(limit);" << endl;
i = v.at(limit + 1);
cout << i << " no exception i = v.at(limit + 1);" << endl;
}
catch (out_of_range& error)
{
cout << "An out of range execption was caught" << endl;
}
}
// 1868783980 no exception for i = v[limit];
// 1868783980 no exception i = v.at(limit);
// An out of range execption was caught
As this example shows not every call will throw exceptions when you might expect. Here the vector's at() call will throw, but the array notation fails silently. Also the at() call does not throw until the caller is off by two rather than off by one.
You have been warned!
I want to leave you with a few tips:
Hints for STL coders.
Don't forget that the "last" iterator points "one past".
For your custom objects, always define:
• a default constructor
• a copy constructor
• operator=
• operator<
• operator==
Objects are copied into contains. The original object still
exist and may need to be deleted.
If it ain't broke break it. Better to learn how the complier complains
when you do know what to fix.
Don't do relational compares on iterators. Only use == or !=.
Don't forget to match the const/non-constness or iterators and
containers.
Watch remove(), it doesn't erase().
Watch nested templates--don't let them look like ">>".
vector<int, allocator<int>> v.
If you use the HP STL implementation beware of init_page_size in
defalloc.h. It allocates 4K for every STL container that is created.
This makes sense on UNIX, but it is probably not what you want.
We have looked at all of the STL container classes and briefly discussed generic algorithms. My hope is that you have enough information to begin to use STL in your code, but the list of items that we have not discussed is longer than the items that we have.
STL is very complex and I have deliberately tried to steer us away from complicating issue. About the issues that we have discussed, I am now ready to take questions.
-----------------
Possible question:
Code Bloat
• Using Adaptors
• Using Pointer-To-Base-Class storage. (This is useful for avoiding code bloat, whether you are using templates or not.)
